//
//  543. 二叉树的直径.swift
//  Top600
//
//  Created by rjb on 2021/7/29.
//

import Foundation
// 主要是谁的左边+右边最大
class Solution543 {
    var result: Int = 0
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        deep(root)
        return result - 1
    }
    @discardableResult
    func deep(_ node: TreeNode?) -> Int {
        guard let root = node else {
            return 0
        }
        let leftDeep = deep(root.left)
        let rightDeep = deep(root.right)
        let nowDeep = max(leftDeep, rightDeep) + 1
        result = max(result, leftDeep + rightDeep + 1)
        return nowDeep
    }
    static func test() {
        let solution = Solution543()
        
        let node1 = TreeNode(1)
        let node2 = TreeNode(2)
        let node3 = TreeNode(3)
        let node4 = TreeNode(4)
        let node5 = TreeNode(5)
        
        node1.left = node2
        node1.right = node3
        node2.left = node4
        node2.right = node5
        
        let result = solution.diameterOfBinaryTree(node1)
        print(result)
    }
}
